|
A left-leaning red–black (LLRB) tree is a type of self-balancing binary search tree. It is a variant of the red–black tree and guarantees the same asymptotic complexity for operations, but is designed to be easier to implement. == Properties of Left Leaning RB == All of the red-black tree algorithms that have been proposed are characterized by a worst-case search time bounded by a small constant multiple of lg N in a tree of N keys, and the behavior observed in practice is typically that same multiple faster than the worst-case bound, close the to optimal lg N nodes examined that would be observed in a perfectly balanced tree. Specifically, in a left-leaning red-black 2-3 tree built from N random keys: * A random successful search examines lg N – 0.5 nodes. * The average tree height is about 2 ln N (!) * The average size of left subtree exhibits log-oscillating behavior. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Left-leaning red–black tree」の詳細全文を読む スポンサード リンク
|